/*
 ------------------------------------------------------------------------------
 Copyright (C) 2009-2011 Eternal Games.

 This file is part of the Eternal Tech source code.

 The Eternal Tech source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The Eternal Tech source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the Eternal Tech source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


//
// r_mesh.cpp - Mesh buffer
//


#include "r_local.h"


/*
 ==============================================================================

    LIST SORTING

 ==============================================================================
*/


/*
 ==================
 R_QSortMeshes
 ==================
*/
static void R_QSortMeshes (mesh_t *meshes, int numMeshes)
{
	mesh_t	tmp;
	int		stack[4096];
	int		stackDepth = 0;
	int		L, R, l, r, median;
	uint	pivot;

	if (numMeshes < 2)
		return;

	L = 0;
	R = numMeshes - 1;

start:
	l = L;
	r = R;

	median = (L + R) >> 1;

	if (meshes[L].sort > meshes[median].sort)
	{
		if (meshes[L].sort < meshes[R].sort) 
			median = L;
	} 
	else if (meshes[R].sort < meshes[median].sort)
		median = R;

	pivot = meshes[median].sort;

	while (l < r){
		while (meshes[l].sort < pivot)
			l++;
		while (meshes[r].sort > pivot)
			r--;

		if (l <= r)
		{
			tmp = meshes[r];
			meshes[r] = meshes[l];
			meshes[l] = tmp;

			l++;
			r--;
		}
	}

	if ((L < r) && (stackDepth < 4096))
	{
		stack[stackDepth++] = l;
		stack[stackDepth++] = R;
		R = r;
		goto start;
	}

	if (l < R)
	{
		L = l;
		goto start;
	}

	if (stackDepth)
	{
		R = stack[--stackDepth];
		L = stack[--stackDepth];
		goto start;
	}
}

/*
 ==================
 R_SortMeshes
 ==================
*/
void R_SortMeshes ()
{
	viewData_t	*viewData = &rg.viewData;
	light_t		*light;
	int			i;

	R_QSortMeshes(&viewData->meshes[viewData->firstMesh], viewData->numMeshes - viewData->firstMesh);
	R_QSortMeshes(&viewData->postProcessMeshes[viewData->firstPostProcessMesh], viewData->numPostProcessMeshes - viewData->firstPostProcessMesh);

	for (i = viewData->firstLight, light = &viewData->lights[viewData->firstLight]; i < viewData->numLights; i++, light++)
	{
		R_QSortMeshes(light->shadows[0], light->numShadows[0]);
		R_QSortMeshes(light->shadows[1], light->numShadows[1]);

		R_QSortMeshes(light->interactions[0], light->numInteractions[0]);
		R_QSortMeshes(light->interactions[1], light->numInteractions[1]);
	}

	for (i = viewData->firstFogLight, light = &viewData->fogLights[viewData->firstFogLight]; i < viewData->numFogLights; i++, light++)
	{
		R_QSortMeshes(light->shadows[0], light->numShadows[0]);
		R_QSortMeshes(light->interactions[0], light->numInteractions[0]);
	}
}


/*
 ==============================================================================

    MESH LIST

 ==============================================================================
*/


/*
 ==================
 R_AddMeshToList
 ==================
*/
void R_AddMeshToList (meshType_t type, meshData_t *data, material_t *material, renderEntity_t *entity)
{
	viewData_t	*viewData = &rg.viewData;
	mesh_t		*mesh;

	if (material->sort != SORT_POST_PROCESS)
	{
		if (viewData->numMeshes == MAX_MESHES)
			Com_Error(ERR_DROP, "R_AddMeshToList: MAX_MESHES hit");

		mesh = &viewData->meshes[viewData->numMeshes++];
	}
	else
	{
		if (viewData->numPostProcessMeshes == MAX_POST_PROCESS_MESHES)
			Com_Error(ERR_DROP, "R_AddMeshToList: MAX_POST_PROCESS_MESHES hit");

		mesh = &viewData->postProcessMeshes[viewData->numPostProcessMeshes++];
	}

	mesh->sort = (material->index << 20) | (entity->index << 9) | (type << 5);
	mesh->data = data;
}

/*
 ==================
 R_ClearMeshLists
 ==================
*/
void R_ClearMeshLists ()
{
	rg.viewData.numMeshes = rg.viewData.firstMesh = 0;
	rg.viewData.numPostProcessMeshes = rg.viewData.firstPostProcessMesh = 0;
}

/*
 ==================
 R_DecomposeSort
 ==================
*/
void R_DecomposeSort (uint sort, material_t **material, renderEntity_t **entity, meshType_t *type, bool *caps)
{
	*material = rg.sortedMaterials[(sort >> 20) & (MAX_MATERIALS-1)];
	*entity = &rg.scene.entities[(sort >> 9) & (MAX_RENDER_ENTITIES-1)];
	*type = (sort >> 5) & 15;
	*caps = sort & 1;
}


/*
 ==============================================================================

    MESH LISTS

 ==============================================================================
*/


/*
 ==================
 R_AddSprite
 ==================
*/
void R_AddSprite (renderEntity_t *entity)
{
	vec3_t	vec;

	if (!entity->customMaterial)
	{
		Com_DevPrintf(S_COLOR_YELLOW "R_AddSprite: NULL customMaterial\n");

		entity->customMaterial = rg.defaultMaterial;
	}

	if (!entity->customMaterial->numStages)
		return;

	// Cull
	if (!r_skipCulling->integerValue)
	{
		VectorSubtract(entity->origin, rg.renderView.viewOrigin, vec);
		if (DotProduct(vec, rg.renderView.viewAxis[0]) < 0)
			return;
	}

	rg.pc.entities++;

	// Add it
	R_AddMeshToList(MESH_SPRITE, NULL, entity->customMaterial, entity);
}

/*
 ==================
 R_AddBeam
 ==================
*/
void R_AddBeam (renderEntity_t *entity)
{
	if (!entity->customMaterial)
	{
		Com_DevPrintf(S_COLOR_YELLOW "R_AddBeam: NULL customMaterial\n");

		entity->customMaterial = rg.defaultMaterial;
	}

	if (!entity->customMaterial->numStages)
		return;

	rg.pc.entities++;

	// Add it
	R_AddMeshToList(MESH_BEAM, NULL, entity->customMaterial, entity);
}

/*
 ==================
 R_AddEntities
 ==================
*/
void R_AddEntities ()
{
	renderEntity_t   *entity;
	model_t			 *model;
	int				 i;

	//if (r_skipEntities->integerValue)
	//	return;

	for (i = 0, entity = rg.renderViewParms.renderEntities; i < rg.renderViewParms.numRenderEntities; i++, entity++)
	{
		switch (entity->reType){
		case RE_MODEL:
			model = entity->model;

			if (!model || model->type == MODEL_BAD)
			{
				Com_DevPrintf(S_COLOR_YELLOW "R_AddEntities: entity with no model at %i, %i, %i\n", (int)entity->origin[0], (int)entity->origin[1], (int)entity->origin[2]);
				break;
			}

			// Development tool
			if (r_singleEntity->integerValue != -1)
			{
				if (r_singleEntity->integerValue != entity->index)
					continue;
			}

			switch (model->type){
			case MODEL_INLINE:
				R_AddInlineModel(entity);
				break;
			case MODEL_MD2:
				R_AddMD2Model(entity);
				break;
			default:
				Com_Error(ERR_DROP, "R_AddEntities: bad modelType (%i)", model->type);
			}

			break;
		case RE_SPRITE:
			R_AddSprite(entity);
			break;
		case RE_BEAM:
			R_AddBeam(entity);
			break;
		default:
			Com_Error(ERR_DROP, "R_AddEntities: bad reType (%i)", entity->reType);
		}
	}
}

/*
 ==================
 R_AddParticles
 ==================
*/
void R_AddParticles ()
{
	renderParticle_t   *particle;
	int				   i;

	//if (r_skipPolys->integerValue)
	//	return;

	for (i = 0, particle = rg.renderViewParms.renderParticles; i < rg.renderViewParms.numRenderParticles; i++, particle++)
	{
		if (!particle->material->numStages)
			continue;

		rg.pc.polys++;

		// Add it
		R_AddMeshToList(MESH_POLY, particle, particle->material, rg.worldEntity);
	}
}